package com.LeeCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 从二叉树一个节点到另一个节点每一步的方向
 */

public class Code2096 {
    public static void main(String[] args) {
        Integer[] arr = {5, 1, 2, 3, null, 6, 4};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(new Code2096().getDirections(root, 3, 6));
    }


    public String getDirections(TreeNode root, int startValue, int destValue) {
        // 获取从根到 start 和 dest 的路径
        List<Character> pathToStart = new ArrayList<>();
        List<Character> pathToDest = new ArrayList<>();

        findPath(root, startValue, pathToStart);
        findPath(root, destValue, pathToDest);

        // 去掉公共前缀（找到最近公共祖先）
        int i = 0;
        while (i < pathToStart.size() && i < pathToDest.size()
                && pathToStart.get(i) == pathToDest.get(i)) {
            i++;
        }

        StringBuilder sb = new StringBuilder();
        // 将 start 上溯到 LCA 的路径替换为 "U"
        for (int j = i; j < pathToStart.size(); j++) {
            sb.append('U');
        }

        // 拼接 LCA 到 dest 的路径
        for (int j = i; j < pathToDest.size(); j++) {
            sb.append(pathToDest.get(j));
        }

        return sb.toString();
    }

    // 辅助函数：使用 DFS 找到从根到目标值的路径
    private boolean findPath(TreeNode node, int target, List<Character> curPath) {
        if (node == null) {
            return false;
        }

        if (node.val == target) {
            return true;
        }

        // 向左走
        curPath.add('L');
        if (findPath(node.left, target, curPath)) {
            return true;
        }

        // 回溯，向右走
        curPath.set(curPath.size() - 1, 'R');
        if (findPath(node.right, target, curPath)) {
            return true;
        }

        // 回溯
        curPath.remove(curPath.size() - 1);
        return false;
    }
}
